package aqs;

import sun.misc.Unsafe;

/*
1、为什么需要AQS？
  锁类型分为：
  1、互斥锁（独占锁）：同一时间只有一个线程能获取锁（ReentrantLock）
  2、共享锁：允许多个线程同时拿到锁（例如：读写锁 ReadWriteLock，写锁和写锁、写锁和读锁互斥，读锁和读锁可以共享）
  这两个类都涉及到线程的互斥问题，这就意味着总会有线程拿不到锁，那么这时为了避免 CPU的资源浪费（一直执行无关的操作 CAS），
所以我们需要将线程阻塞，既然涉及到了线程阻塞操作，那么必然会有唤醒操作。
  所以我们需要：
  1、存放等待线程的数据结构：队列
  2、操作线程阻塞和唤醒的方法：LockSupport类（提供 park、unpark 线程的方法）
  3、表示当前锁的状态：state变量：0无锁、1有锁
  所以AQS的出现就是对于互斥锁、共享锁的抽象：队列 + state

2、什么是公平锁？什么是非公平锁
  1、公平锁：FIFO（先进先出），根据AQS的排队的队列来看，是否有线程在排队，如果没有，那么抢锁，如果有那么排队。
  2、非公平锁：直接抢，管他有没有线程排队。

3、什么是抢锁？
  AQS的实现有一个state变量，将其争夺修改为1，那么这种争夺的行为叫做抢锁。

4、怎么抢锁？抢锁的实现方式是什么？
  CAS：Compare And Swap，比较并交换。compareAndSetState(0, 1)
  1.目标变量的当前的值（1.当前的实例，2.实例变量的内存地址偏移量），2.预期的旧值，3.要更新的新值。
  CAS：Lock（锁定）主内存的值，比较并替换。
通过CAS操作，会对主内存的值加锁（Lock锁），此时只能有一个线程去访问主内存。
   CPU指令："lock; cmpxchg(void* ptr, int old, int new)"。
lock指令前缀，会设置处理器的LOCK#信号，这个信号会使总线锁定，阻止其他处理器接管总线访问内存，直到使用lock前缀的指令执行结束，
这会使这条指令的执行变为原子操作。
在多处理器环境下，设置LOCK#信号，能保证某个处理器对共享内存的独占使用。
  修改主内存的值成功，抢锁成功；改失败，抢锁失败。
  保证了抢锁的线程安全性。

*/
//AQS方法。抽象类
public abstract class AbstractQueuedSynchronizer {
    private volatile int state; //状态变量
    private transient volatile Node head; //先进先出链表的队列
    private transient volatile Node tail;

    //protected：子类需要实现。
    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException(); //不支持的操作
    }

    static final class Node {
        //指示节点正在独占模式下等待
        static final Node EXCLUSIVE = null;

        volatile Node prev;
        volatile Node next;
        volatile Thread thread;
        Node nextWaiter;

        Node() {    // Used to establish initial head or SHARED marker
        }

        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }
    }

    //获取锁的方法
    public final void acquire(int arg) {
        /*  !tryAcquire(arg)：根据模板方法设计模式，AQS实现了完整的排队，阻塞，唤醒算法，
          但是AQS并不知道应不应该去执行这些操作，它需要子类来判定是否获取锁成功。
            而这里的tryAcquire方法就是子类实现，告知AQS获取到了锁吗？
          如果返回false，那么这里是!（取反）操作，所以会继续执行&&（与操作符）后面的操作，就是 排队->阻塞。
            tryAcquire()是子类实现，判断是否获取锁成功。
        */
        if (!tryAcquire(arg) &&
                acquireQueued(
                        addWaiter(Node.EXCLUSIVE)//将当前线程包装，放入等待队列中。Node.EXCLUSIVE，节点的类型为互斥锁类型。表明锁类型为互斥锁。
                        , arg)
                ) // 阻塞
            selfInterrupt();
    }

    //enq：将节点插入队列。enqueue：入队。
    //包装线程，放入队列
    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode); //包装线程
        // Try the fast path of enq; backup to full enq on failure
        // 尝试快速方式的入队；         失败了，就（返回）去执行候补的完整的入队方式（enq(node);）
        // 此时，队列已经初始化，直接进行CAS操作。进行优化。不需要初始化，直接CAS。
        Node pred = tail;
        if (pred != null) {//队列已经初始化
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {//CASTail
                pred.next = node;
                return node;
            }
        }
        enq(node); //放入队列
        return node;
    }

    //节点入队。将节点插入队列
    private Node enq(final Node node) {
        //for (; ; ) 一看死循环，必有分支！分支就是初始化操作 和入队操作。
        for (; ; ) {
            //队列。根据数据结构描述，有队头和队尾。
            //head变量表示队列头部，tail表示队列尾部；总是从尾部入队，头部出队。
            Node t = tail; //t：队列的之前的最后一个节点
            if (t == null) { //t为null，此时尾引用tail不存在，那么此时队列没有初始化，则进行初始化。
                //初始化链表。
                if (compareAndSetHead(new Node()))//CAS保证了多线程安全，将其头部初始化为Node空节点。
                    tail = head;//尾部初始指向头部
            } else { //入队操作
                //prev和next。根据数据结构，这是双向链表。prev：当前节点的前驱节点；next：后继节点。
                node.prev = t;//① prev，新节点的前驱指针，指向队列的之前的最后一个节点。
                //compareAndSetTail(t, node)，执行成功，则尾引用tail指向了node数据的地址。
                //多线程同时插入操作，竞争点是哪个变量？ tail引用是竞争点。
                //多线程同时插入操作，竞争点在哪里？
                //compareAndSetTail：比较tail引用指向的地址，和t引用指向的地址；如果相同，则将tail引用指向node引用指向的地址。
                //compareAndSetTail：比较tail引用指向的地址，和t引用指向的地址；如果相同，则将node变量保存的地址写入tail变量。
                //多线程竞争tail指针，保证并发插入的安全性。
                if (compareAndSetTail(t, node)) {//② tail，队列的队尾指针，指向新节点。
                    //争用tail指针成功后，关联next指针。
                    t.next = node;//③ next，队列的之前的最后一个节点的后继指针，指向新节点。
                    return t;
                }
            }
        }
    }

    final boolean acquireQueued(final Node node, int arg) {
        return true;
    }

    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long headOffset;
    private static final long tailOffset;

    static {
        try {
            headOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("tail"));

        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    //目标变量的当前的值（1.当前的实例，2.实例变量的内存地址偏移量），2.预期的旧值，3.要更新的新值。
    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }
}
